package 中等.搜索.深度优先搜索;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 有两个水壶，容量分别为 jug1Capacity 和 jug2Capacity 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 targetCapacity 升。
 * 如果可以得到 targetCapacity 升水，最后请用以上水壶中的一或两个来盛放取得的 targetCapacity 升水。
 * 你可以：
 * 装满任意一个水壶
 * 清空任意一个水壶
 * 从一个水壶向另外一个水壶倒水，直到装满或者倒空
 *
 * @ https://leetcode.cn/problems/water-and-jug-problem/description/?envType=daily-question&envId=2024-01-28
 * @date 2024/01/28
 */
public class 水壶问题_365 {

    public static void main(String[] args) {

    }

    private Map<Integer, Set<Integer>> map = new HashMap<>();

    private int jug1Capacity, jug2Capacity, targetCapacity;

    /**
     * 深度优先搜索
     */
    public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        this.jug1Capacity = jug1Capacity;
        this.jug2Capacity = jug2Capacity;
        this.targetCapacity = targetCapacity;

        return dfs(0, 0);
    }

    /**
     * 代表水壶1当前有 jug1 升水，水壶2当前有 jug2 升水时，是否可以得到 targetCapacity 升水
     * 深度搜索的下一个节点
     * 1，装满任意一个水壶
     * 2，清空任意一个水壶
     * 3，从一个水壶向另外一个水壶倒水，直到装满或者倒空
     */
    private boolean dfs(int jug1, int jug2) {
        if (jug1 + jug2 == targetCapacity) {
            return true;
        }

        Set<Integer> set = map.get(jug1);
        if (set == null) {
            set = new HashSet<>();
            map.put(jug1, set);
        }
        if (map.get(jug1).contains(jug2)) {
            return false;
        }
        set.add(jug2);
        boolean flag = false;

        if (jug1 < jug1Capacity) {
            flag = flag || dfs(jug1Capacity, jug2);
        }
        if (jug2 < jug2Capacity) {
            flag = flag || dfs(jug1, jug2Capacity);
        }
        if (jug1 > 0) {
            flag = flag || dfs(0, jug2);
        }
        if (jug2 > 0) {
            flag = flag || dfs(jug1, 0);
        }
        if (jug1 > 0 && jug2 < jug2Capacity) {
            int replace = Math.min(jug1, jug2Capacity - jug2);
            flag = flag || dfs(jug1 - replace, jug2 + replace);
        }
        if (jug2 > 0 && jug1 < jug1Capacity) {
            int replace = Math.min(jug2, jug1Capacity - jug1);
            flag = flag || dfs(jug1 + replace, jug2 - replace);
        }
        return flag;
    }

}
